/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025/6/2
 * Time: 21:23
 */

public class Solution {
    private static int i = 0;
    private static TreeNode createTree(int[] array) {
        int cur = array[i];
        TreeNode root = null;
        if (cur != -1) {
            root = new TreeNode(cur);
            i++;
            root.left = createTree(array);
            root.right = createTree(array);
        }else {
            i++;
        }
        return root;
    }
    public static int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        int ret = rootSum(root, targetSum);
        //遍历每一个节点
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public static int rootSum(TreeNode root, long targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        }

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
    public static void main(String[] args) {
        TreeNode root = createTree(new int[]{10, 5, 3, 3, -1, -1, -2, -1, -1, 2, -1, 1, -1, -1, -3, -1, 11, -1, -1});
        int num = pathSum(root, 8);
        System.out.println(num);
    }
}